\chapter{预备知识}
\label{chap:prelim}

在第\ref{chap:intro}章中已对深度学习模型计算图替换的基本概念有了初步的介绍，但是这种介绍比较模糊。为了明确这些概念，需要给出其数学定义，这为后续介绍了GSL语言设计与实现的细节提供了基础。本章中定义的符号可参见主要符号对照表。

\section{工作负载}
\label{sec:workload}

一般而言，一个深度学习模型由两个部分组成：其一是模型的网络结构，描述了模型的数据所需经过的所有计算；其二是模型的参数，是指模型在训练过程中学习到的，并在推理过程中参与运算的所有数据。网络可以表达为一个函数，该函数同时接受模型的输入和模型的参数作为输入。记模型的输入数据序列为$X^i=\langle x^i_1, x^i_2, \dots, x^i_n\rangle$，参数序列为$X^\theta=\langle x^\theta_1, x^\theta_2, \dots, x^\theta_m\rangle$，两个序列中的所有元素均为张量，则该函数$F$可记作
\begin{equation}
    F(X^i, X^\theta)=F(x^i_1, x^i_2, \dots, x^i_n, x^\theta_1, x^\theta_2, \dots, x^\theta_m)
    \label{eq:net}
\end{equation}

\begin{definition}[工作负载]
    \label{def:workload}
    一个网络$F$及其对应模型参数$\Theta$组成的二元组称为一个工作负载，记为$W$，即
    \begin{equation}
        W = (F,\Theta)
        \label{eq:workload}
    \end{equation}
\end{definition}

注意式\ref{eq:net}中的$X^\theta$为$F$的形式参数，而式\ref{eq:workload}中的$\Theta=\langle\theta_1, \theta_2, \dots, \theta_m\rangle$为实际的参数张量，一个工作负载的实际参数序列中的元素$\theta_i$必须和其网络的形式参数序列中的元素$x^\theta_i$一一对应，其张量形状和数据类型必须匹配。

在运行一个工作负载时，接受外部提供的输入序列$X^i$，并且将其和参数序列$\Theta$一起传递给网络函数$F$，由$F$计算结果。工作负载可看作一个以输入序列$X^i$为参数的函数，其表达式为
\begin{equation}
    W(X^i) = F(X^i, \Theta)
\end{equation}

这里需要区分一个工作负载中所涉及的输入数据、模型参数、超参数和常量等概念。输入数据$X$是指工作负载运行时从外部接收的数据。模型参数$\Theta$的规模由网络结构决定，并且在模型训练完毕后确定其具体值，储存在工作负载中。超参数是人为指定、用于决定网络结构的数据，在网络中表现为参数的类型或算子的属性。常量是在网络定义时确定的，是网络的一部分，不包含在模型参数中。

\section{计算表达式}
\label{sec:expr}

\subsection{语言定义}

在\ref{sec:workload}中提到了一个网络可以用一个函数来表示，那么这个函数是如何来表达网络的结构呢？本节将从程序语言的角度对函数的具体形式进行探讨。由于文本中还会涉及到其它语言，这里将描述网络结构的语言称为计算表达式语言，其形式上是一个表达式，描述的内容是深度学习网络的计算结构。

由于深度学习涉及的计算一般是无状态的，即一个算子的计算结果只和输入的状态相关，而和系统状态无关，本文中用类似函数式语言的方式来对其进行建模。这和Relay IR\cite{roesch2019relay}对于深度学习网络结构的描述方式是一致的，不过本文中所涉及的计算表达式语言更为简化。本文中的计算表达式仅覆盖无循环的静态网络，不包括结构在运行时才确定的动态网络，也不包括循环神经网络等中含有环的网络。

设计算表达式语言的元变量为$e$，所有计算表达式所构成的集合为$\mathcal{E}$。考虑网络函数$F$，设其输入数据为$x^i_1, x^i_2, \dots, x^i_n$，模型参数为$x^\theta_1, x^\theta_2, \dots, x^\theta_m$，那么它可以表示成一个匿名函数，具有下列的形式：
\begin{equation}
    \mathtt{fn}\ (x^i_1, x^i_2, \dots, x^i_n, x^\theta_1, x^\theta_2, \dots, x^\theta_m)\ \{e\}
\end{equation}
其中$e$是函数的主体部分，具体描述了网络的结构。图\ref{fig:expr_syn}给出计算表达式的BNF语法。

\begin{figure}[htbp]
    \begin{alignat*}{4}
         & e & \quad & \models     & \quad & v                                                    & \quad & \text{常量}     \\
         &   &       & \mathrel{|} &       & x\ \{\mathtt{shape}=v, \mathtt{dtype}=v\}            &       & \text{变量} \\
         &   &       & \mathrel{|} &       & op\ (e, e, \dots, e)\ \{l_1=v, l_2=v, \dots, l_m=v\} &       & \text{算子调用} \\
         &   &       & \mathrel{|} &       & (e, e, \dots, e)                                     &       & \text{元组构成} \\
         &   &       & \mathrel{|} &       & e.i                                                  &       & \text{元组投影}
    \end{alignat*}
    \caption{计算表达式的BNF语法}
    \label{fig:expr_syn}
\end{figure}

从图\ref{fig:expr_syn}中可知，计算表达式具有五种基本形式。常量就是一个编译期确定的值$v$，该值可具有多种形式：标量、张量、元组、字符串等。变量就是网络的形式参数，包括输入数据与模型参数，变量表达式包含张量形状\texttt{shape}和数据类型\texttt{dtype}两个属性，属性的定义见定义\ref{def:attr}。算子调用表达式描述了调用一个深度学习算子时所提供的输入数据与属性。其中$op$为已知的算子，$(e_1, e_2, \dots, e_n)$为输入参数，$\{l_1=v_1, l_2=v_2, \dots, l_m=v_m\}$给出了调用表达式的所有属性条目。元组构成表达式与元组投影表达式均和元组相关，分别表达了构建一个元组和从元组中取某个元素的行为。元组的引入，能够很好地表达算子可变输入参数（如张量连接算子）和多个返回值（如批归一化算子），是不可缺少的语言特性。

下面给出和计算表达式相关的一个概念——属性的定义。

\begin{definition}[属性]
    \label{def:attr}
    属性为一键值对$(l, v)$，本文中常记为$l=v$，其中$l$为一字符串，表示属性的名称，$v$为一常量，表示属性的值。
\end{definition}

属性是表达式内在、固有的，并决定表达式行为的参数项目。在计算表达式的各种形式中，最为明显的是变量和算子调用表达式的属性字典储存的一系列属性条目，这些都是计算表达式的属性。此外，元组投影表达式$e.i$的索引$i$也可以认为是一种属性，本文中称其为\texttt{index}。定义函数$attr(e)$表示获取计算表达式$e$的属性字典。

\subsection{子表达式}

根据计算表达式的语法，一个表达式可以由若干其它表达式所组成的。为了描述表达式之间的包含关系，这里给出子表达式的相关概念。

\begin{definition}[直接子表达式]
    定义计算表达式集合$\mathcal{E}$上的关系$\sqsubset_i$：$e_1\sqsubset_i e_2$表示$e_1$是$e_2$的第$i$个直接子表达式，其推理规则由图\ref{fig:direct_subexpr}给出。
\end{definition}

\begin{figure}[htbp]
    \begin{multicols}{2}
        \begin{equation}
            \inferrule{e=op\ (e_1, e_2, \dots, e_n)\ \{\dots\}}{e_i\sqsubset_i e, i\in 1..n}
            \tag{\textsc{DS-Call}}
        \end{equation}
        \begin{equation}
            \inferrule{e=(e_1, e_2, \dots, e_n)}{e_i\sqsubset_i e, i\in 1..n}
            \tag{\textsc{DS-Tuple}}
        \end{equation}
        \begin{equation}
            \inferrule{ }{e_1\sqsubset_1 e_1.i}
            \tag{\textsc{DS-Proj}}
        \end{equation}
    \end{multicols}
    \caption{直接子表达式的推理规则}
    \label{fig:direct_subexpr}
\end{figure}

在计算表达式中，一个表达式$e_1$可以是多个表达式的直接子表达式，即可能存在$e_2\neq e_3$使得$e_1\sqsubset_i e_2, e_1\sqsubset_j e_3$。由于表达式可以共享，需要对表达式的相等关系做出规定。两个计算表达式相等，当且仅当它们来自同一处定义。否则，即使两个表达式具有完全相同的形式，它们也不相等。

\begin{definition}[子表达式]
    定义计算表达式集合$\mathcal{E}$上的关系$\subseteq$：$e_1\subseteq e_2$表示$e_1$是$e_2$的子表达式，其推理规则由\ref{fig:subexpr}给出。
\end{definition}

\begin{figure}[htbp]
    \begin{multicols}{2}
        \begin{equation}
            \inferrule{ }{e\subseteq e}
            \tag{\textsc{SE-Reflex}}
        \end{equation}
        \begin{equation}
            \inferrule{e_1\subseteq e_2 \\ e_2\sqsubset_i e_3}{e_1\subseteq e_3}
            \tag{\textsc{SE-Trans}}
        \end{equation}
    \end{multicols}
    \caption{子表达式的推理规则}
    \label{fig:subexpr}
\end{figure}

\section{计算图及其替换}
\label{sec:graph}

\subsection{计算图}

在\ref{sec:expr}节中介绍了计算表达式，为表达网络的计算提供了一种规范的方法。然而，这种形式不能直观地表达网络的结构特点，包括算子的组合方式、数据的依赖关系等。对于网络的结构，可以使用图的方式来表达这些信息。本文中，计算图指的就是计算表达式的图表达，下面给出计算图的定义。

\begin{definition}[计算图]
    计算图$G=(V, E)$为一张有向无环图（Directed Acyclic Graph，DAG）。$V$为顶点集，顶点$v\in V$表示运算；$E$表示边集，有向边$\langle u, v\rangle\in E$表示数据的依赖关系，$u$为$v$的前驱，$v$为$u$的后继。图中无前驱、非常量顶点称为输入顶点，图的输入顶点序列$\mathbf{v}^i = \langle v^i_1, v^i_2, \dots, v^i_m \rangle$；图中无后继的顶点称为输出顶点，图的输出顶点序列$\mathbf{v}^o = \langle v^o_1, v^o_2, \dots, v^o_n \rangle$。
    \label{def:comp_graph}
\end{definition}

本文中，计算图的边直接用$\langle u, v\rangle$表示，不使用单个符号$e$，以免与计算表达式的元变量冲突。而$v$可能与计算表达式中的值元变量存在冲突，但其含义根据其使用环境不同往往可以明确。

对于计算图中的每个顶点，可以定义其可达顶点集。

\begin{definition}[可达顶点集]
    对于计算图$G$的顶点$v$，$u$是$v$的可达顶点当且仅当有一条从$u$到$v$的路径，所有满足该条件的顶点$u$所构成的集合称为顶点$v$的可达顶点集，记作$R(v)$。
\end{definition}

和一般意义上的有向图不同的是，计算图的每个顶点需要指定其前驱的顺序，这是因为每个前驱对应着一个运算中不同位置的输入数据，下面给出前驱序列的定义。

\begin{definition}[前驱序列]
    对于一张计算图$G=(V, E)$的每个顶点$v\in V$记录其前驱序列$pred(v)=\langle u_1, u_2, \dots, u_n\rangle$。对于任意一条边$\langle u, v\rangle \in E$，$u$必然有$u\in pred(v)$。对于任意$u_i\in pred(v)$，必然存在一条边$\langle u_i, v \rangle \in E$。
    \label{def:pred_seq}
\end{definition}

下面讨论计算表达式与计算图的对应关系。一个表达式一定可以用一张计算图表示；但由于一张计算图可能有多个输出顶点，它可能对应多个表达式。所以，应该考虑表达式序列$\mathbf{e}=\langle e_1, e_2, \dots, e_n\rangle$与计算图$G=(V, E)$的对应关系，即考虑一个双射函数$\mathscr{F}$，它可以进行计算表达式序列与计算图之间的映射。

下面介绍$\mathscr{F}$是如何将$\mathbf{e}$和$G$进行一一对应的。对于表达式序列中每一个元素的子表达式$e$满足$\exists i: e\subseteq e_i, e_i\in\mathbf{e}$都有一个计算图顶点$v\in V$与之对应，反之亦然。每一个顶点$v$需要存储必要的信息，如顶点类型、属性等，使其可以还原到表达式。设表达式与计算图顶点的映射为$f$，对于$e$的所有直接子表达式$e_{d,j}\sqsubset_j e$，在计算图中都有一条边$\langle u, v\rangle=\langle f(e_{d, j}), f(e)\rangle\in E$与之对应，且$u$为$pred(v)$的第$j$个元素，反之亦然。

计算表达式与计算图本质上描述的都是深度学习网络，而其各自有其表达上的优势：计算表达式形式明确、易于推理，计算图能够直观地表达网络的结构特点。在本文讨论网络时，会选择其中一种形式展开。由于存在$\mathscr{F}$这一映射，总能将其转换成另一种形式。

\subsection{逆后序}

\SetKwFunction{Init}{Init}
\SetKwFunction{Visit}{Visit}

图的遍历是图算法的重要基础，对于计算图而言，其最重要的遍历便是逆后序遍历。本文中的计算图对顶点的前驱的先后顺序作了规定，对一个顶点前驱的访问必须按照其在前驱序列中的顺序，这使得遍历的顺序唯一确定。算法\ref{alg:rev_post}展示了逆后序遍历的基本模式。其中\Init 定义算法的初始化工作，\Visit 定义访问每个顶点的行为。基于逆后序遍历的算法，只需要定义这两个函数即可，不需要重新编写逆后序遍历的过程。规定了逆后序遍历方式后，下面给出逆后序序列的定义。

\begin{definition}[逆后序序列]
    \label{def:rpo}
    对于计算图$G$，其逆后序序列$rpo(G)$为按算法\ref{alg:rev_post}访问各顶点的序列。
\end{definition}

\SetKwProg{Fn}{function}{}{}

\begin{algorithm}[tb]
    \caption{计算图逆后序遍历的算法模式}
    \label{alg:rev_post}

    \KwData{计算图$G$，其输出顶点序列为$\mathbf{v}^o$}
    \KwResult{根据具体算法确定}

    $S\leftarrow\emptyset$\;
    \BlankLine

    \Fn{\Init{}}{
        \dots
    }
    \BlankLine

    \Fn{\Visit{$v$}}{
        \dots
    }
    \BlankLine

    \SetKwFunction{Trav}{Traverse}
    \Fn{\Trav{$v$}}{
        \If{$v\in S$}{
            \textbf{return}
        }
        \For{$u_i\in pred(v)$}{
            \Trav{$u_i$}
        }
        \Visit{$v$}\;
        $S\leftarrow S\cup\{v\}$\;
    }
    \BlankLine

    \Init{}\;
    \For{$v^o_j\in \mathbf{v}^o$}{
        \Trav{$v^o_j$}\;
    }
\end{algorithm}

定义\ref{def:pred_seq}中定义了顶点的前驱序列，相对应的，一个顶点也有若干后继，在一般的有向图中，每个顶点的后继也是不确定的。在定义了逆后序序列后，可以为顶点的后继也规定一个顺序。

\begin{definition}[后继序列]
    \label{def:succ_seq}
    对于计算图$G=(V, E)$的每个顶点$v\in V$记录其后继序列$succ(v)=\langle w_1, w_2, \dots, w_n \rangle$。对于任意一条边$\langle v, w\rangle \in E$，必然有$w\in succ(v)$。对于任意$w_i\in succ(v)$，必然存在一条边$\langle v, w_i\rangle \in E$。任意顶点$v$的后继序列$succ(v)$必须是$rpo(G)$的子序列。
\end{definition}

由于规定了顶点的后继序列必须是计算图逆后序序列的子序列，所以该序列必须是唯一的。顶点的后继序列可以通过算法\ref{alg:succ_seq}构造，其中$append(s, v)$表示将顶点$v$追加到序列$s$末尾。

\begin{algorithm}[tb]
    \caption{构造计算图顶点的后继序列（基于算法\ref{alg:rev_post}）}
    \label{alg:succ_seq}

    \KwData{计算图$G=(V, E)$}
    \KwResult{顶点的后继序列$succ(v), v\in V$}

    \Fn{\Init{}}{
        \ForEach{$v\in V$}{
            $succ(v)\leftarrow \langle\rangle$\;
        }
    }
    \BlankLine

    \Fn{\Visit{$v$}}{
        \For{$u_i\in pred(v)$}{
            $succ(v)\leftarrow\ append(succ(u_i), v)$\;
        }
    }
\end{algorithm}

\subsection{计算图替换}

本节中介绍计算图替换的相关概念。Fang等人\cite{fang2020ocggs}最早对计算图替换进行了形式化的定义，本文参考了这一定义，并根据所定义的计算图进行一定的修改。首先，给出模式图与图替换规则的定义，然后再定义图替换。

\begin{definition}[模式图]
    模式图$G_p=(V_p, E_p)$是连通的有向无环图，具有输入顶点序列$\mathbf{v}^i_p$与输出顶点序列$\mathbf{v}^o_p$。对于每个顶点$v_p\in V_p$记录其前驱序列$pred(v_p)=\langle v_{p,1}, v_{p,2}, \dots, v_{p,n}\rangle$。
\end{definition}

由于模式图和计算图十分接近，也可以在其上定义可达顶点集$R(v_p)$，进行逆后序遍历，以及定义后继序列$succ(v_p)$，这里不再展开。

\begin{definition}[图替换规则]
    一条图替换规则记作$\phi=(G_s, G_t)$。$G_s$与$G_t$都是模式图，$G_s$称为源模式图，$G_t$称为目标模式图。设$G_s$的输入与输出顶点序列分别为$\mathbf{v}^i_s$与$\mathbf{v}^o_s$，$G_t$的输入与输出顶点序列分别为$\mathbf{v}^i_t$与$\mathbf{v}^o_t$，要求$\mathbf{v}^i_s=\mathbf{v}^i_t$，$|\mathbf{v}^o_s|=|\mathbf{v}^o_t|=n$，且对于任意$k\in1..n$，$v^o_{s, k}$与$v^o_{t, k}$相对应。对于$G_s$，若$n>1$则需要满足
    \begin{equation}
        \label{eq:src_connect}
        \forall k\in2..n: \left[\bigcup_{j=1}^{k-1} R(v^o_{s,j})\right] \cap R(v^o_{s,k})\neq \emptyset
    \end{equation}
    \label{def:subst_rule}
\end{definition}

定义\ref{def:subst_rule}中需要注意源模式图与目标模式图输入输出顶点的对应关系。源模式与目标模式图必须具有完全相同的输入顶点序列，目标模式不能增加或丢弃输入顶点。同时，源模式图的输出顶点必须与目标模式图的输出顶点一一对应，否则无法使用该规则来改写计算图。式\ref{eq:src_connect}要求对于源模式图第$k$个输出顶点，其可达顶点必须和前$k-1$个输出顶点可达顶点并集的交集不为空，该式对多输出顶点的源模式图的连通性作出了规定。

\begin{definition}[图替换]
    给定一计算图$G=(V, E)$以及一条替换规则$\phi=(G_s, G_t)$，一次图替换记作$\tau=(\phi, f, g)$。$f$是从源模式图$G_s$到匹配子图$G_m$的双射映射，$g$是从目标模式图$G_t$到改写后子图$G_r$的双射映射。$f$与$g$都是从图到图的映射，可以看作从一张图$G_1=(V_1, E_1)$的顶点集与边集的并集$V_1\cup E_1$到另一张图$G_2=(V_2, E_2)$的顶点集与边集的并集$V_2\cup E_2$的映射。

    $f$需要满足下列条件：
    \begin{enumerate}
        \item $G_m$为$G$的子图；
        \item 对于任意$v\in V_s$，$v$与$f(v)$的顶点类型及属性匹配；
        \item 对于任意顶点$v\in V_s$，如果$pred(v)=\langle u_1, u_2, \dots, u_n \rangle$，那么必有$pred(f(v)) = \langle f(u_1), f(u_2), \dots, f(u_n) \rangle$；
        \item 不存在一条边$\langle u, v \rangle \in E$使得$u\in V_m-\mathbf{v}^i_m-\mathbf{v}^o_m, v\notin V_m$。
    \end{enumerate}

    $g$需要满足下列条件：
    \begin{enumerate}
        \item 对于任意$v\in V_t$，$v$与$g(v)$的顶点类型及属性匹配；
        \item 对于任意顶点$v\in V_t$，如果$pred(v)=\langle u_1, u_2, \dots, u_n \rangle$，那么必有$pred(g(v)) = \langle g(u_1), g(u_2), \dots, g(u_n) \rangle$。
    \end{enumerate}
    \label{def:subst}
\end{definition}

上述定义的核心是两个双射映射$f$和$g$，分别表达了进行图替换所需进行的两个步骤：匹配和改写。这两个函数都要求顶点类型与属性的匹配，以及保持前驱的顺序。此外，$f$还要求所映射到的图必须是原图的子图，否则不能称为一次匹配。$f$的第4个条件要求原图中不能存在一条从匹配子图非输入输出顶点指向非匹配子图顶点的边，这是为了保证子图的完全替换，使得替换后的计算图不会依然包含$V_m$的顶点。

\section{本章小结}

本章主要介绍了计算图替换的预备知识。首先介绍了工作负载的概念，然后定义了描述网络计算的语言——计算表达式，并定义了直接子表达式、子表达式这两个计算表达式集合上的关系。在此基础上，定义了计算图的结构，探讨了计算图与计算表达式的相互转化。介绍了遍历计算图的顺序——逆后序遍历，规定了逆后序遍历算法的基本框架。最后，定义了替换规则和图替换。
